/*
Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.
*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


 //Definition for singly-linked list.
 struct ListNode {
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
 };

class Solution {
public:
	ListNode* deleteDuplicates(ListNode* head) {

		if (head == NULL || head->next == NULL)
		{
			return head;
		}

		ListNode *p = new ListNode(-1);
		ListNode *q = new ListNode(-1);

		p = head;
		q = head->next;
		
		head->next = NULL;
		ListNode *pre = new ListNode(-1);
		pre = head;

		while (q!=NULL)
		{
			if (p->val != q->val)
			{
				ListNode *temp = new ListNode(p->val);
				pre->next = temp;
				pre = pre->next;
				p = q;
				q = p->next;
			}
			else
			{
				while (q != NULL && (p->val == q->val))
				{
					q = q->next;
				}
				p = q;
				if (q != NULL)
				{
					q = p->next;
				}

			}
		}

		if (p != NULL)
		{
			ListNode *temp = new ListNode(p->val);
			pre->next = temp;
		}
		head = head->next;

		return head;
	}
};

int main()
{
	cout << "Remove Duplicates from Sorted List II:  " << endl;

	int length;
	cout << "Input the length of the List: " << endl;

	cin >> length;

	//vector<int> nums;

	ListNode *head = new ListNode(-1);
	ListNode *p = new ListNode(-1);
	
	p = head;

	while (length--)
	{
		int element;
		cin >> element;
		ListNode *q = new ListNode(element);
		p->next = q;
		p = p->next;
		//nums.push_back(element);
	}

	head = head->next;

	Solution s;

	head = s.deleteDuplicates(head);

	cout << "The result: " << endl;

	system("pause");

	return 0;
}